typedef struct
{
    int data[N];
    int top;
} stack;
typedef struct node
{
    int adjvex; //邻接点域
    struct node *next;
    //指向下一个邻接点（或边）的指针域
    int info;
    //若要表示边上信息，则应增加相关数据域info
} EdgeNode; //边结点
typedef struct vnode
{
    VertexType vertex;   //顶点域
    EdgeNode *firstedge; //第一条边的指针
} VertexNode;            //顶点结点
typedef struct{
    VertexNode AdjList[N]; //顶点结点向量
}ALGraph;

#pragma region  【算法5 - 14】求AOE 网中各顶点事件的最早发生时间
int ve[N] = {0}, vl[N], e[E], l[E];
int VertexElyTime(VertexNode AdjList[N], Stack *T)
{ // AOE网G采用邻接表存储结构
  //求各顶点事件的最早发生时间ve(全局变量)
  // T为拓扑序列顶点栈，S为零入度顶点栈
  // 若G无回路，则用栈T返回G的一个拓扑序列，且函数值为1，否则为0
    Stack S;
    S.top = -1; //初始化零入度顶点栈S
    count = 0;
    for (i = 0; i < N; i++) //将初入度为0的顶点入栈
        if (AdjList[i].indegree == 0)
        {
            S.data[S.top] = i;
            S.top++;
        }
    while (S.top != -1) //当入度为0的顶点栈不空时
    {
        j = S.data[S.top];
        S.top--;
        T->data[T->top] = j;
        T->top++; //进入拓扑序列
        count++;  //计数进入拓扑序列的点
        for (p = AdjList[j].firstedge; p; p = p->next)
        //修改顶点j的邻接点的入度
        {
            k = p->adjvex; //顶点j邻接到的顶点k的入度减1
            AdjList[k].indegree--;
            if (AdjList[k].indegree == 0)
            //顶点k的入度减1后若减为0, 则入栈
            {
                S.data[S.top] = k;
                S.top++;
            }
            if ((ve[j] + (p->info)) > ve[k])
                //是否修改顶点k的最早发生时间
                ve[k] = ve[j] + (p->info);
        }
    }
    if (count < N)
        return 0;
    //该有向网有回路返回0，否则返回1
    else
        return 1；
}
#pragma endregion
#pragma region 【算法5 - 15】 求出AOE 网的关键活动
int PivotalPath(ALGraph *G){
    //G为AOE网，用邻接表存储，求出G的各项关键活动
    char tag;
    int i,j;
    stack *T;
    T=(stack *)malloc(sizeof(stack));
    T->top=-1;
    if(!VertexElyTime(G,T))return 0;
    for(i=0;i<N;i++)vl[i]=ve[N-1];
    while(T->top!=-1){
        j=T->data[T->top];
        T->top--;
        for(p=G->AdjList[j].firstedge; p;p=p->next){
            k=p->adjvex;
            if(vl[k]-p->info<vl[j]){
                vl[j]=vl[k]-p->info;
            }
        }
    }
    printf("顶点1 顶点2 权值 最早 最迟 是否关键活动\n");
    for(j=0lj<N;j++){
        for(p=G->AdjList[j].firstedge;p;p=p->next){
            k=p->adjvex;
            dut=p->info;
            e=ve[j];l=vl[k]-dut;
            if(e==l)tag='*';
            esle tag=' ';
            //输出各个活动的最早和最迟开始时间，有*的为关键活动
            printf("%d->%d:  %d  %d  %d  %c\n",j,k,dut,e,l,tag);
        }
    }
    return 1;
}
#pragma endregion